/* 
 COMP20007 Design of Algorithms 

 Module to supply a graph data structure for Assignment 2.
 The graph is stored as an adjacency matrix, with
 vetrices as unsigned integers indexing an array of .
 lists that store edges.

 Author: Andrew Turpin (aturpin@unimelb.edu.au)
 Date: Aprin 2013

*/

typedef list_t * LabelList;
typedef struct {
    unsigned int in_degree;
    unsigned int out_degree;    // should equal length of neighbours list
    LabelList neighbours;       // outgoing edges
    char *text;                 // text fragmetn for this vertex
} Vertex;

typedef struct {
    unsigned int m;            // number of edges in graph
    Vector *vertices;          // array of vertices indexed by label
} Graph;

#define VERTEX(_g, _i) ((Vertex *)vector_get((_g)->vertices, _i))

Graph * create_graph();                             // create an empty graph
unsigned int get_number_of_edges(Graph *g);         // return number of edges in g
void print_graph(Graph *g);                         // print graph
Label add_vertex(Graph *g, char *s);                // add a new vertex with text s and return label
void insert_edge(Graph *g, Label u, Label v);     // add (u,v) to g

Label find_end(Graph *g);   // find vertex with out_degree == 0, else n+1
Label find_start(Graph *g); // find vertex with in_degree == 0, else n+1

LabelList find_euler_path(Graph *g, Label start);

void print_path(Graph *g, LabelList path);
